Міністерство освіти і науки України Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій Кафедра програмного забезпечення / ЗВІТ Про виконання лабораторної роботи №7 «Порівняння методів сортування» з дисципліни «Алгоритми і структури даних» Лектор: доц. кафедри ПЗ Коротєєва Т.О.  ТЕМА: Порівняння методів сортування. МЕТА: Порівняти вивчені раніше алгоритми сортування. Побудувати таблицю і графік швидкодії таких алгоритмів сортування. Зробити висновки щодо застосовності цих алгоритмів. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Алгоритм, алгорифм (латинізоване «Algorithmi», від імені узбецького математика IX століття аль-Хорезмі) — система правил виконання обчислювального процесу, що обов’язково приводить до розв’язання певного класу задач після скінченного числа операцій. При написанні комп’ютерних програм алгоритм описує логічну послідовність операцій. Поняття алгоритму належить до первісних понять математики. Обчислювальні процеси алгоритмічного характеру (арифметичні дії над цілими числами, знаходження найбільшого спільного дільника двох чисел тощо) відомі людству з глибокої давнини. Проте в явному вигляді поняття алгоритму сформувалося лише на початку XX століття. Термін сортування (англійською «Sorting») означає розділення елементів за певними ознаками (сортами) і не дуже точно описує поставлену задачу. Більш точним була б назва впорядкування (англійською «Ordering»), але через перевантаженість слова «порядок» (англійською «Order») різними значеннями, в цьому контексті ним не скористалися. Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів. На практиці елементи, що впорядковуються, рідко бувають просто числами. Набагато частіше, кожен такий елемент є записом (англійською «Record»). В кожному записі є ключ (англійською «Key»), по якому власне і здійснюється впорядкування, в той же час є й інша супутня інформація. Алгоритм сортування на практиці має бути реалізований так, щоб разом з ключами переміщати і супутню інформацію. Якщо кожен запис містить супутню інформацію великого об’єму, то з метою звести до мінімуму переписування великих об’ємів інформації, впорядкування відбувається не у самому масиві елементів, а в масиві вказівників на елементи. Сам метод сортування не залежить від того, чи впорядковуються тільки числа, чи також і супутня інформація, тому при описі алгоритмів для простоти припускають, що елементи є числами. Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є обчислювальна та ємнісна складність. Крім цих двох характеристик, сортування поділяють на стабільні та нестабільні, з використанням додаткової інформації про елементи, чи без використання. Стабільним (англійською «Stable») називається такий алгоритм сортування, що не змінює порядок елементів з однаковим ключем. Для значної кількості алгоритмів середній і найгірший час впорядкування масиву з n елементів є O(n2), це пов’язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час O(n∙log(n)). В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного. Теорема про найкращий час сортування стверджує, що якщо алгоритм сортування в своїй роботі спирається тільки на операції порівняння двох об’єктів (≤) і не враховує жодної додаткової інформації про елементи, то він не може впорядкувати масив елементів швидше ніж за O(n∙log(n)) в найгіршому випадку. Довести цю теорему нескладно. На кожному кроці алгоритм проводить одне порівняння, результатом якого є один з двох варіантів: 1. A ≤ B. 2. A > B. В залежності від результату порівняння алгоритм буде виконувати подальші дії. Значить, всю роботу алгоритму можна представ...